Introduction

• Many mathematical ideas begin with simple questions about whole numbers.
• One of the most surprising facts is that the greatest common divisor of two numbers can be written using only multiplication and addition.
• This fact is called the Bézout Identity, and it sits at the heart of number theory.
• In this chapter, we explore what the identity says, why it’s true, and how to find the special numbers involved.

A First Look at Integer Combinations

• Suppose you have two whole numbers, say $a$ and $b$.
• You can form new numbers by taking expressions like $$ax + by$$ where $x$ and $y$ are integers (positive, negative, or zero).
• These are called integer linear combinations of $a$ and $b$.
• Examples:
  • $3(4) + (-2)(6) = 12 - 12 = 0$
  • $5(7) + 1(3) = 38$
• A natural question: Which numbers can be made this way?

This question leads directly to Bézout’s Identity.

The Greatest Common Divisor Revisited

• The greatest common divisor of two integers $a$ and $b$ is the largest integer that divides both.
• Notation: $\gcd(a,b)$.
• Examples:
  • $\gcd(12, 18) = 6$
  • $\gcd(8, 20) = 4$
• Key facts (informal):
  • The gcd is always positive.
  • The gcd does not change if you replace a number by a multiple of it plus the other number.
  • The gcd measures the “shared structure” of two numbers.

These facts are the foundation of the Euclidean Algorithm.

The Euclidean Algorithm

A fast method for computing $\gcd(a,b)$:

• Divide $a$ by $b$ and record the remainder. $$a = bq + r$$
• Replace $(a,b)$ with $(b,r)$.
• Repeat until the remainder is $0$.
• The last nonzero remainder is the gcd.

Example: compute $\gcd(56, 15)$

Step 1: divide $56$ by $15$: $$56 = 15 \cdot 3 + 11$$ Step 2: divide $15$ by $11$: $$15 = 11 \cdot 1 + 4$$ Step 3: divide $11$ by $4$: $$11 = 4 \cdot 2 + 3$$ Step 4: divide $4$ by $3$: $$4 = 3 \cdot 1 + 1$$ Step 5: divide $3$ by $1$: $$3 = 1 \cdot 3 + 0$$ So the last nonzero remainder is $1$, hence $$\gcd(56, 15) = 1.$$ However, this process also hides something deeper: it can be reversed.

The Extended Euclidean Algorithm

The extended version does everything the Euclidean Algorithm does, and it finds integers $x$ and $y$ such that: $$ax + by = \gcd(a,b).$$

How it works:

• Perform the Euclidean Algorithm as usual.
• Then work backwards, expressing each remainder as a combination of earlier numbers.
• Eventually, you express the gcd itself as a combination of $a$ and $b$.

Example:

Step A: start from the last nonzero remainder

From Step 4: $$4 = 3 \cdot 1 + 1$$ Rearranged: $$1 = 4 - 3 \cdot 1.$$ Right now, $1$ is written in terms of $4$ and $3$.

Step B: express $3$ in terms of $11$ and $4$

From Step 3: $$11 = 4 \cdot 2 + 3$$ Rearranged: $$3 = 11 - 4 \cdot 2.$$ Substitute this into the expression for $1$:

• We had $1 = 4 - 3 \cdot 1$.
• Replace $3$ with $11 - 4 \cdot 2$: $$\begin{aligned} 1 &= 4 - (11 - 4 \cdot 2) \\ &= 4 - 11 + 4 \cdot 2 \\ &= 4 \cdot 3 - 11. \end{aligned}$$

So now: $$1 = 4 \cdot 3 - 11.$$ Now $1$ is in terms of $4$ and $11$.

Step C: express $4$ in terms of $15$ and $11$

From Step 2: $$15 = 11 \cdot 1 + 4$$ Rearranged: $$4 = 15 - 11.$$ Substitute this into $1 = 4 \cdot 3 - 11$:

• Replace $4$ with $15 - 11$: $$\begin{aligned} 1 &= (15 - 11) \cdot 3 - 11 \\ &= 15 \cdot 3 - 11 \cdot 3 - 11 \\ &= 15 \cdot 3 - 11 \cdot 4. \end{aligned}$$

So now: $$1 = 15 \cdot 3 - 11 \cdot 4.$$ Now $1$ is in terms of $15$ and $11$.

Step D: express $11$ in terms of $56$ and $15$

From Step 1: $$56 = 15 \cdot 3 + 11$$ Rearranged: $$11 = 56 - 15 \cdot 3.$$ Substitute this into $1 = 15 \cdot 3 - 11 \cdot 4$:

• Replace $11$ with $56 - 15 \cdot 3$: $$\begin{aligned} 1 &= 15 \cdot 3 - 4(56 - 15 \cdot 3) \\ &= 15 \cdot 3 - 4 \cdot 56 + 4 \cdot 15 \cdot 3 \\ &= 15 \cdot 3 + 15 \cdot 12 - 4 \cdot 56 \\ &= 15(3 + 12) - 4 \cdot 56 \\ &= 15 \cdot 15 - 4 \cdot 56. \end{aligned}$$

So we have: $$1 = 15 \cdot 15 - 56 \cdot 4.$$ Rewriting in the standard order: $$1 = 56(-4) + 15(15).$$ This is the heart of Bézout’s Identity.

Statement of the Bézout Identity

The Bézout Identity says:

• For any integers $a$ and $b$, there exist integers $x$ and $y$ such that
• $$ax + by = \gcd(a,b).$$

Important points:

• The numbers $x$ and $y$ are called Bézout coefficients.
• They are not unique — there are infinitely many pairs.
• The identity works for all integers, even negative ones.
• The extended Euclidean Algorithm always finds one valid pair.

Interpreting Bézout Coefficients

What do the coefficients $x$ and $y$ mean?

• They show how the gcd is built from $a$ and $b$.
• They reveal a hidden structure: the gcd is the smallest positive integer that can be written as $ax + by$.
• They tell us that integer combinations of $a$ and $b$ form a whole “family” of numbers.
• They also show up in many applications

Examples of Bézout’s Identity in Action

Example 1: $\gcd(12, 18)$

• $\gcd(12,18)=6$.
• One Bézout identity is $$6 = 12( -1 ) + 18( 1 ).$$

Example 2: $\gcd(21, 14)$

• $\gcd(21,14)=7$.
• One identity is $$7 = 21(1) + 14(-1).$$

Example 3: $\gcd(56, 15)$

• From earlier: $$1 = 56(-4) + 15(15).$$

Example 4: Negative numbers

• $\gcd(-9, 6) = 3$.
• A Bézout identity is $$3 = (-9)(1) + 6(2).$$

These examples show how flexible the identity is.

Summary and Key Ideas

• Integer combinations $ax + by$ form a structured set of numbers.
• The gcd is the smallest positive number in that set.
• The Euclidean Algorithm computes the gcd efficiently.
• The extended version finds Bézout coefficients $x$ and $y$.
• Bézout’s Identity ties everything together: $$ax + by = \gcd(a,b).$$
• These ideas are the foundation for solving equations like $ax + by = c$

Calculator

Exercises

1. Compute $\gcd(30, 18)$ using the Euclidean Algorithm.
   • Then find integers $x$ and $y$ such that $30x + 18y = \gcd(30,18)$.

   Solution

   Compute $\gcd(30,18)$ and find $x,y$ such that $30x + 18y = \gcd(30,18)$.

   • Euclidean Algorithm:
     • $30 = 18\cdot 1 + 12$
     • $18 = 12\cdot 1 + 6$
     • $12 = 6\cdot 2 + 0$
     → $\gcd(30,18)=6$.
   • Back‑substitution:
     • $6 = 18 - 12$
     • $12 = 30 - 18$
     Substitute: $$6 = 18 - (30 - 18) = 2\cdot 18 - 30.$$

   One solution:

   • $x = -1$
   • $y = 2$
2. Use the extended Euclidean Algorithm to find one Bézout identity for $\gcd(99, 78)$.

   Solution

   Find a Bézout identity for $\gcd(99,78)$.

   • Euclidean Algorithm:
     • $99 = 78\cdot 1 + 21$
     • $78 = 21\cdot 3 + 15$
     • $21 = 15\cdot 1 + 6$
     • $15 = 6\cdot 2 + 3$
     • $6 = 3\cdot 2 + 0$
     → $\gcd(99,78)=3$.
   • Back‑substitution (compressed): $$3 = 99(-11) + 78(14).$$

   One solution:

   • $x = -11$
   • $y = 14$
3. Verify that the pair $(x,y)$ you found in Exercise 2 actually satisfies the identity.

   Solution

   Verify the identity from Exercise 2.

   Check:

   • $99(-11) = -1089$
   • $78(14) = 1092$
   • Sum: $-1089 + 1092 = 3$

   Correct.

4. Find a Bézout identity for $\gcd(25, 10)$ and explain why the coefficients are not unique.

   Solution

   Find a Bézout identity for $\gcd(25,10)$ and explain non‑uniqueness.

   • $\gcd(25,10)=5$
   • One identity: $$5 = 25(1) + 10(-2).$$

   Why not unique?

   • If $(x,y)$ is a solution, then $$(x + 2t,\; y - 5t)$$ is also a solution for any integer $t$.
5. Compute $\gcd(101, 23)$ and express it as a combination of $101$ and $23$.

   Solution

   Compute $\gcd(101,23)$ and express it as a combination.

   • Euclidean Algorithm:
     • $101 = 23\cdot 4 + 9$
     • $23 = 9\cdot 2 + 5$
     • $9 = 5\cdot 1 + 4$
     • $5 = 4\cdot 1 + 1$
     • $4 = 1\cdot 4 + 0$
     → $\gcd(101,23)=1$.
   • Back‑substitution (compressed): $$1 = 101(5) + 23(-22).$$

   One solution:

   • $x = 5$
   • $y = -22$
6. Let $a=14$ and $b=9$.
   • Compute $\gcd(a,b)$.
   • Find one pair $(x,y)$ such that $14x + 9y = \gcd(14,9)$.

   Solution

   For $a=14$, $b=9$:

   • Euclidean Algorithm:
     • $14 = 9\cdot 1 + 5$
     • $9 = 5\cdot 1 + 4$
     • $5 = 4\cdot 1 + 1$
     • $4 = 1\cdot 4 + 0$
     → $\gcd(14,9)=1$.
   • Back‑substitution (compressed): $$1 = 14(-2) + 9(3).$$

   One solution:

   • $x = -2$
   • $y = 3$
7. True or false: If $\gcd(a,b)=1$, then there exist integers $x$ and $y$ such that $ax + by = 1$.

   Solution

   True or false: If $\gcd(a,b)=1$, then there exist integers $x,y$ such that $ax + by = 1$.

   • True.
   • This is exactly the Bézout Identity.
8. Challenge: Find a Bézout identity for $\gcd(123, 45)$.

   Solution

   Find a Bézout identity for $\gcd(123,45)$.

   • Euclidean Algorithm:
     • $123 = 45\cdot 2 + 33$
     • $45 = 33\cdot 1 + 12$
     • $33 = 12\cdot 2 + 9$
     • $12 = 9\cdot 1 + 3$
     • $9 = 3\cdot 3 + 0$
     → $\gcd(123,45)=3$.
   • Back‑substitution (compressed): $$3 = 123(-7) + 45(19).$$

   One solution:

   • $x = -7$
   • $y = 19$